1. Field of the Invention
The present invention relates to performing computational operations within computer systems. More specifically, the present invention relates to a method and an apparatus for efficiently performing modular division over binary polynomial fields and/or prime integer fields.
2. Related Art
Modular division is a commonly performed operation in elliptic-curve cryptographic algorithms. For example, a modular division operation for the polynomial field GF(2N) takes as inputs two elements X(t) and Y(t) of GF(2N), both represented as binary polynomials in t of degree less than N, and an irreducible polynomial M(t) in GF(2N). The modular division operation produces a residue R(t), which is also an element of GF(2N). This residue R(t) is defined by the equation R(t)=Y(t)/X(t) mod M(t).
Note that binary polynomials can be represented by long bit strings, which makes arithmetic operations easy to implement. For example, in GF(2N) additions and subtractions can be implemented by a bit-wise exclusive-OR operation. Also, dividing a polynomial A(t) by t, denoted by A(t)/t, is simply a right-shift operation of the bit string representing A(t). Within this specification, the bit string representing A(t) is represented as A and the operation A(t)/t is represented as shift(A). Furthermore, a comparison of polynomials is equivalent to the comparison of their bit strings as integers.
One problem in performing modular division is that existing techniques require the constituent sub-operations to be performed in sequence, without exploiting possible parallelism. Another problem is that existing techniques typically require comparison operations between large binary numbers, which can be extremely time-consuming.
What is needed is a method and an apparatus for performing a modular division operation without the above-described problems.